import java.util.Collection;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 * 二叉搜索树
 */
class BinarySearchTree {

    static class TreeNode { //定义树节点
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root = null;

    /**
     * 查找一个 val 是不是在当前的搜索树中
     * @param val 要查询的元素
     * @return 有--返回，没有--返回 null
     */
    public TreeNode search(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if(val > cur.val) {
                cur = cur.right;
            }else if(val < cur.val) {
                cur = cur.left;
            }else { //找到了
                return cur;
            }
        }
        return null;
    }

    /**
     * 插入元素 key
     * @param key 要插入的元素
     * @return 成功插入返回 true，否则 false
     */
    public boolean insert(int key) {
        if(root == null) {
            root = new TreeNode(key);
            return true;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            if(key > cur.val) {
                parent = cur;
                cur = cur.right;
            }else if(key < cur.val) {
                parent = cur;
                cur = cur.left;
            }else {
                return false; //遇到了相同的key，不能插入了
            }
        } //cur为null了，可以开始插入key了
        TreeNode node = new TreeNode(key);
        if(key < parent.val) {
            parent.left = node;
        }else {
            parent.right = node;
        }
        return true;
    }

    /**
     * 中序遍历
     * @param root 根节点
     */
    public void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");;
        inorder(root.right);
    }

    public void remove(int key) {
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            if(key == cur.val) {

            }else if(key > cur.val) { //向右边走
                parent = cur;
                cur = cur.right;
            }else {  //向左边走
                parent = cur;
                cur = cur.left;
            }
        }
    }

    /**
     * 删除某一个节点
     * @param parent 父节点
     * @param cur 要删除的节点
     * 要删除cur，就让cur的父节点指向cur的子节点
     */
    private void removeNode(TreeNode parent, TreeNode cur) {
        // 1.cur的左边为空 --- 有3种情况
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            }else if(cur == parent.left) {  // 这里实在不理解可以画图一目了然
                parent.left = cur.right;
            }else { //cur == parent.right
                parent.right = cur.right;
            }
        // 2.cur的右边为空 --- 有3种情况
        }else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            }else if(cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        // 3.cur的左右都不为空
        }else {
            TreeNode target = cur.right; //从cur右边开始找
            TreeNode targetParent = cur;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            //找到了右子树的最左边的那个节点
            cur.val = target.val; //将target的值给cur，然后删除target
            if(target == targetParent.left){  //也就是这个target是一个最左边的叶子结点
                targetParent.left = target.right;  // 因为已经是最左边的节点了，所以只可能会有右孩子节点。
                            // 将target的右孩子赋给targetParent，如果有就赋给它，没有就是赋给null，那么就是删除了
            }else { //不是最左边的叶子结点，虽然是一个最左边的节点，但是它自己还有一个右孩子节点
                targetParent.right = target.right;
            }


        }
    }

}

public class Main {
    public static void main1(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        int[] array = {5,3,4,1,7,8,2,6,0,9};
        //将数组中的元素全部插入搜索二叉树中
        for (int i = 0; i < array.length; i++) {
            binarySearchTree.insert(array[i]);
        }
        //通过中序遍历判断插入是否正确
        binarySearchTree.inorder(binarySearchTree.root);
    }

    public static void main2(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        // 往treeMap里边存放元素时候，key一定是要可比较的，在这里指的是String是可以比较的
        // 因为这是一个搜索二叉树，搜索二叉树存放的时候都是要比较的
        map.put("hello", 2);
        map.put("abc", 4);
        System.out.println(map);

        int v = map.get("hello");
        System.out.println(v);

        Integer v1 = map.getOrDefault("he",100); //如果有这个key打印val，没有打印给定的默认值
        System.out.println(v1);

        System.out.println("取出所有的key值，进行组织，通过set变为一个集合：(用Set接收)");
        Set<String> set = map.keySet();
        System.out.println(set);
        System.out.println();

        System.out.println("取出所有的value值，进行组织，通过set变为一个集合：(用Collection接收)");
        Collection<Integer> collection = map.values();
        System.out.println(collection);
        System.out.println();
    }

    public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("hello", 2);
        map.put("abc", 4);

        // 返回所有的 key-value 映射关系
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();//entrySet里边存放的是所有的key-value映射关系
        for (Map.Entry<String,Integer> entry : entrySet) { // entry是其中的一个 key-value
            System.out.println("key："+entry.getKey()+"   val："+entry.getValue());
        }
    }
}
